package mycollections.list;

import java.util.Comparator;
import java.util.RandomAccess;

public class MyCollections {
    public static <T extends Comparable<? super T>> void sort(MyList<T> list) {
        Comparator<T> defaultComparator = new Comparator<T>() {
            @Override
            public int compare(T o1, T o2) {
                return o1.compareTo(o2);
            }
        };
        if (list instanceof RandomAccess) {
            quickSort(list, defaultComparator, 0, list.size()-1);
        } else {
            bubbleSort(list, defaultComparator);
        }
    }

    public static <T> void sort(MyList<T> list, Comparator<? super T> comparator) {
        if (list instanceof RandomAccess) {
            quickSort(list, comparator, 0, list.size()-1);
        } else {
            bubbleSort((MyLinkedList) list, comparator);
        }
    }

    public static <T> void swap(MyList<T> list, int i, int j) {
        T tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }

    public static <T extends Comparable<? super T>> int binarySearch(MyArrayList<T> list, T o) {
        return binarySearch(list, o, new Comparator<T>() {
            @Override
            public int compare(T o1, T o2) {
                return o1.compareTo(o2);
            }
        });
    }

    public static <T> int binarySearch(MyArrayList<T> list, T o, Comparator<T> comparator) {
        return binarySearch(list, o, comparator, 0, list.size());
    }

    private static <T> int binarySearch(MyArrayList<T> list, T o, Comparator<T> comparator, int start, int end) {
        int m = (start + end) >> 1;
        if (start >= end)
            return start;
        if (comparator.compare(list.get(m), o) == 0)
            return m;
        if (comparator.compare(o,list.get(m)) < 0) {
            return binarySearch(list, o, comparator, start, m);
        } else
            return binarySearch(list, o, comparator, m + 1, end);
    }

    private static <T> void bubbleSort(MyList<T> list, Comparator<? super T> comparator) {
        MyLinkedList linkedList = (MyLinkedList<T>) list;
        if (linkedList.size() > 1) {
            MyLinkedList.Node i = linkedList.last;
            while (i.prev != null) {
                MyLinkedList.Node j = linkedList.first;
                while (j != i) {
                    if (comparator.compare((T) j.item, (T) j.next.item) > 0) {
                        swapInNodes(j.next, j);
                    }
                    j=j.next;
                }
                i = i.prev;
            }
        }
    }

    private static void swapInNodes(MyLinkedList.Node a, MyLinkedList.Node b) {
        Object tempItem = a.item;
        a.item = b.item;
        b.item = tempItem;
    }

    private static <T> void quickSort(MyList<T> l, Comparator<? super T> comparator, int startIndex, int finishIndex) {
        int begin = startIndex, end = finishIndex;
        if (startIndex>finishIndex)
            return;
        T p = (T) l.get((startIndex + finishIndex) >> 1);
        while (begin <= end) {
            while (comparator.compare((T) l.get(begin), p) < 0)
                begin++;
            while (comparator.compare((T) l.get(end), p) > 0)
                end--;
            if (begin <= end) {
                swap(l, begin, end);
                begin++;
                end--;
            }
        }
        if (startIndex < end)
            quickSort(l, comparator, startIndex, end);
        if (begin < finishIndex)
            quickSort(l, comparator, begin, finishIndex);
    }


    public static<T> void copy(MyList<? super T> dest, MyList<? extends T> src) {
        dest.clear();
        for (T o : src)
            dest.add(o);
    }

    public static void reverse(MyList<?> l) {
        if (l instanceof RandomAccess) {
            for (int i = 0; i < l.size() >> 1; i++) {
                swap(l, i, l.size() - i - 1);
            }
        } else {
            MyLinkedList.MyIterator ascIter = (MyLinkedList.MyIterator) l.iterator(), descIterator = (MyLinkedList.MyIterator) ((MyLinkedList) l).descendingIterator();
            for (int i = 0; i < l.size() >> 1; i++, ascIter.next(), descIterator.next()) {
                swapInNodes(ascIter.current, descIterator.current);
            }
        }
    }

}
